﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1.Algorithm
{
    public class KMPtest    //KMP，一种高效的字符串匹配检索方式
    {
        public void KMPFunc()
        {
            string targetStr = "poiuytrhjgboiabcdefghijkliob";
            string patternStr = "abcdefghijkl";

            var t = new Stopwatch();
            t.Start();
            int targetIndex = BFMatch(targetStr, patternStr);
            t.Stop();
            Console.WriteLine("BFmatch result:{0}, cost time:{1}ms", targetIndex, t.Elapsed.Milliseconds);

        }

        //暴力匹配Brute-Force BF算法
        //首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。
        //时间复杂度O(mn)
        private int BFMatch(string targetStr,string patternStr)
        {
            int targetIndex = -1;    //模仿IndexOf()方法，返回匹配字符串的第一个字符的索引值
            bool matchFlag = false;
            char[] targetArr = targetStr.ToCharArray();
            char[] patternArr = patternStr.ToCharArray();

            //                  模式串的最大长度m-n即可，小于n的部分必定不能匹配                 
            for (int i = 0; i <= targetArr.Length-patternArr.Length; i++)
            {
                for (int j = 0; j < patternArr.Length; j++)
                {
                    if (patternArr[j] == targetArr[i + j])
                    {
                        matchFlag = true;
                    }
                    else
                    {
                        matchFlag = false;
                        break;
                    }
                }
                if (matchFlag)  //匹配到了就终止检索
                {
                    targetIndex = i;
                    break;
                }
            }

            return targetIndex;
        }

        private void KMPMatch(string targetStr, string patternStr)
        {
            bool matchFlag = false;
            char[] targetArr = targetStr.ToCharArray();
            char[] patternArr = patternStr.ToCharArray();


        }


    }
}
